package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class _17_Solution {

    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                char preChar = s.charAt(i - 1);
                if (preChar == '(') {
                    if (i > 1) {
                        dp[i] = 2 + dp[i - 2];
                        dp[i-1] = dp[i];
                    } else {
                        dp[i] = 2;
                        dp[i-1] = 2;
                    }
                } else {
                    int preIndex = -1;
                    for (int j = i-1; j >= 0; j--) {
                        if (dp[j] == 0) {
                            if (s.charAt(j) == '(') {
                                preIndex = j;
                            }
                            break;
                        }
                    }
                    if (preIndex == -1) {
                        dp[i] = 0;
                    } else {
                        if (preIndex == 0) {
                            dp[i] = dp[i - 1] + 2;
                            dp[preIndex] = dp[i];
                        } else {
                            dp[i] = dp[i-1]+dp[preIndex-1]+2;
                            dp[preIndex] = dp[i];
                        }

                    }
                }
            }
        }
        int max = dp[0];
        for (int i : dp) {
            max = Math.max(max,i);
        }
        return max;
    }

    @Test
    public void test(){
        String str = "()(()()";
//        String str = "()(())";
        System.out.println(longestValidParentheses(str));
    }
}
